package day190827;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/8/27 下午 06:23
 */
public class CountBits {

    /**
     * F(n) = F(n/2) + n%2
     * @param num
     * @return
     */
    public int[] countBits(int num) {
        int[] dp = new int[num + 1];
        dp[0] = 0;
        for (int i = 1; i <= dp.length; i++) {
            if (i % 2 == 0) {
                dp[i] = dp[i / 2] + 1;
            } else {
                dp[i] = dp[i - 1] + 1;
            }
        }
        return dp;
    }


}
